package main

import (
	"fmt"
)

/**
执行用时：16 ms, 在所有 Go 提交中击败了99.17%的用户
内存消耗：6.7 MB, 在所有 Go 提交中击败了19.14%的用户
 */
func searchMatrix(matrix [][]int, target int) bool {

	n, m := len(matrix), len(matrix[0])
	i, j := 0, m - 1
	for i < n && j >= 0 {
		t := matrix[i][j]
		if t == target { return true }
		if t < target {
			i++
 		} else {
			j--
		}
	}
	return false
}

func main() {

	matrix := [][]int{
		{1, 4, 7, 11, 15},
		{2, 5, 8, 12, 19},
		{3, 6, 9, 16, 22},
		{10, 13, 14, 17, 24},
		{18, 21, 23, 26, 30},
	}
	fmt.Println(searchMatrix(matrix, 5))  // true
}
